package Graph.graphWithNoweight.bfs;

import Graph.graphWithNoweight.dfs.Graph;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @Author: 蔡翔
 * @Date: 2020/2/8 10:12
 * @Version 1.0
 */
public class GraphBFS {
    private Graph G;
    private boolean[] visited;
    private ArrayList<Integer> order = new ArrayList<>();

    public GraphBFS(Graph G){
        this.G = G;
        visited = new boolean[G.V()];
        for(int i=0;i<G.V();i++){
            if(!visited[i]){
                bsf(i);
            }
        }
    }

    private void bsf(int s) {
        Queue<Integer> queue = new LinkedList<>();
        visited[s] = true;
        queue.add(s);
        while (!queue.isEmpty()){
            Integer v = queue.remove();
            order.add(v);
            for(Integer w:G.adj(v)){
                if(!visited[w]){
                    queue.add(w);
                    visited[w] = true;
                }
            }
        }
    }

    public Iterable<Integer> order(){
        return order;
    }

    public static void main(String[] args) {
        Graph g = new Graph("g.txt");
        GraphBFS graphBFS = new GraphBFS(g);
        System.out.println(graphBFS.order());
    }
}
